package structure.array;


import java.util.HashSet;
import java.util.Set;

/**
 * 地址：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
 * <p>
 * 题目：剑指 Offer 03. 数组中重复的数字
 * <p>
 * 找出数组中重复的数字。
 * <p>
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 * <p>
 * 示例 1：
 * <p>
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 */
public class Leetcode_Sword_Offer_03 {
    public static void main(String[] args) {

        int[] input = new int[]{2, 3, 1, 0, 2, 5, 3};

        System.out.println(findRepeatNumber(input));


    }

    /**
     * 解法2：
     * 思路： 根据值去找下标。
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * <p>
     * 考虑边界条件：
     * 1、数组为空
     * <p>
     * <p>
     * 执行结果：通过
     执行用时：1 ms, 在所有 Java 提交中击败了 83.76% 的用户
     内存消耗：46.3 MB, 在所有 Java 提交中击败了 51.08% 的用户
     * <p>
     * <p>
     *
     * @param nums
     * @return
     */
    public static int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length){
            if(nums[i] == i){
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i] ){
                return nums[i];
            }
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return -1;
    }


    /**
     * 解法1：
     * 思路： 只需要找任意一个重复的数字即可。
     * 用容器 Set 来存储。
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     * <p>
     * 考虑边界条件：
     * 1、数组为空
     * <p>
     * <p>
     * 执行结果：通过
     * 执行用时：7 ms, 在所有 Java 提交中击败了 36.15% 的用户
     * 内存消耗：47.4 M , 在所有 Java 提交中击败了 26.39% 的用户
     * <p>
     * <p>
     * 可以优化的地方在哪里？
     * 空间复杂度：原地交换
     *
     * @param nums
     * @return
     */
    public static int findRepeatNumber1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (set.contains(i)) {
                return i;
            }
            set.add(i);
        }
        return 0;
    }
}
